The present invention relates to a system and method for facilitating access to and use of geographic data used with a navigation application program that provides navigating features and functions to an end-user, and more particularly, the present invention relates to a geographic database, and an architecture therefor, that provides for the identification and use of named intersections so that a navigation application program using the geographic database can accommodate identification and use of named intersections thereby facilitating certain functions for an end-user of the navigation application program and enhancing performance of the navigation system. The present invention also relates to an improved process for forming substitute data records to represent complex physical geographic features, thereby facilitating operation of a navigation system by reducing processing requirements for certain functions.
Computer-based navigation application programs are available that provide end-users (such as drivers of vehicles in which the navigation systems are installed) with various navigating functions and features. For example, some navigation application programs are able to determine an optimum route to travel by roads between locations in a geographic region. Using input from an end-user, and optionally from equipment that can determine one's physical location (such as a GPS system), a navigation application program can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in a geographic region. The navigation application program may then provide the end-user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end-user to travel from the starting location to the destination location. If the navigation system is located in an automobile, the instructions may take the form of audio instructions that are provided along the way as the end-user is traveling the route. Some navigation application programs are able to show detailed maps on computer displays outlining routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, the navigation application program uses one or more detailed databases that include data which represent physical features in a geographic region. The detailed database may include data representing the roads and intersections in a geographic region and also may include information relating to the represented the roads and intersections in a geographic region, such as turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on.
One difficulty in providing geographic data for use by a navigation application program relates to the efficient utilization of the available computer resources of the navigation system on which the navigation application program is run. Computerbased navigation application programs are provided on various platforms including some with relatively limited computer hardware resources. For example, navigation systems may be located in vehicles or may be hand-held. These types of navigation systems may have relatively limited computer resources, such as limited memory and relatively slow I/O. In order to provide a high a level of functionality in such systems, it is required that the available computer resources be used efficiently.
The limited resources of some navigation systems can affect the ability of these types of navigation systems to provide desired functions, especially when using a geographic database that includes a relatively high level of detail. For example, a geographic database can include data that accurately represent all the physical geographic features that form a complex intersection in a geographic region, including all the ramps, entrances, exits, internal pathway links (and geographic coordinates thereof), turn restrictions between links, speed limits, and so on. However, for some complex intersections, a relatively large amount of data is necessary to represent all the actual physical features of the intersection. Handling such large amounts of data may adversely affect the performance of navigation systems with limited resources.
Another consideration related to the use of geographic data by navigation systems is that given the relatively large size of the geographic database necessary to provide a desired level of functionality to the end-user, all the data records for an entire geographic region cannot be loaded into the memory of the navigation system at the same time. This is especially true for navigation system platforms with limited resources, such as systems installed in vehicles or hand-held systems. Due to the limited memory resources of these navigation systems, it is necessary to load geographic data as needed from a storage medium, such as a CD-ROM disk, into the memory of the navigation system for use by the navigation application program. Unfortunately, as mentioned above, in these types of systems, I/O access from a storage medium may also be relatively slow. Thus, the relatively limited memory resources combined with the relatively slow I/O can limit the performance of some types of navigation systems, resulting in slow response. Aside from being undesirable, slow response in a navigation system may render the system useless for its intended purpose in certain circumstances. For example, if the navigation system is installed in a vehicle, the driver may require information from the navigation system about a desired route in a matter of seconds in order to utilize the information while driving. If the navigation system requires more than several seconds to calculate a route, the driver may have moved beyond the point at which the routing information provided by the navigation system is relevant. Therefore, it is important that navigation systems operate efficiently in order to provide navigating information relatively quickly.
Navigation application programs may also be run on computer platforms that have in general greater memory resources and faster I/O, such as personal computers networks. Although these systems may have more and faster resources, the considerations related to the efficient use of geographic data still apply, but on a larger scale. With these types of systems, even greater functionality can be provided if the limitations imposed by memory size and I/O are minimized.
Techniques have been devised or implemented to improve navigation system performance by organizing, structuring, or arranging the geographic database or the data in the database in particular ways. Because a navigation system uses geographic data in certain known and expected ways to perform known functions, the geographic data can be organized, structured, or arranged in a manner that facilitates their use in these known ways by the navigation system.
When an end-user uses a navigation system to find a route between a starting destination and a desired destination, the end-user may be required to provide input to the navigation system identifying the desired destination (and possibly a starting location). The navigation system may provide suitable user-interface hardware, such as a keypad, a keyboard, a touch-sensitive screen, voice recognition equipment, and so on, by which the end-user may input this information to the navigation system. The navigation application also includes suitable user-interface program that enables the end-user to identify the desired destination or starting location to the navigation system. Navigation system programming may provide various ways by which the end-user can identify the desired destination or starting location. One way that an end-user may identify a desired location to the navigation system is by street address. If the navigation system uses a positioning system, such as a GPS system or a dead-reckoning system, to determine a present position, the starting location of a route may be obtained from the positioning system. After a starting position and a desired destination have been identified to the navigation system, appropriate programming in the navigation system calculates one or more routes between these two locations.
A potential disadvantage of requiring an end-user to identify a desired destination location by street address is that the end-user may not know the street address of the desired destination. For example, an end-user may want the navigation system to determine a route to a museum but does not know the street address of the museum.
Some navigation systems allow an end-user to identify a destination by means other than a street address. An end-user may identify a desired destination location or starting location to the navigation system by first querying the navigation system for a particular known point-of-interest by name or type and then selecting the desired point-of-interest from a result set provided by the navigation system to the end-user. In order to provide these kinds of features to an end-user, the navigation system may use a oeographic database that supports these kinds of searches.
By providing this kind of functionality, navigation systems can provide useful features to end-users. However, there is still a need for improvement. One area in which there exists a need for improvement is in accommodating different ways by which locations are identified or used. In many geographic regions, people have developed different ways to identify locations and to provide directions to locations. in many regions, it is common to refer to well known intersections by name. The intersection name may be an official name or may be a name that has developed over the years by common usage. One kind of intersection that is commonly named is a roundabout. Also, intersections of two or more interstate highways are sometimes referred to by name. Although an end-user's desired destination may not be located exactly at such a named intersection, an end-user may want a navigation system to provide directions to such an intersection. Accordingly, it is desired that a navigation system provide a way to accommodate the identification of intersections by name.
It is an objective therefore to provide an improved means by which navigation systems can accommodate use by end-users. It is also an objective to provide improvements in the storage or use of geographic data that improves performance in a navigation system. Similarly, it is a further objective to develop navigation functions that can exploit the geographic database in improved ways.